package cn.njupt.unionfind;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

//泛型并查集
public class GenericUnionFind<E> {

    private Map<E,Node<E>> map=new HashMap<>();

    public void makeSets(E e){
        if(map.containsKey(e))return;
        map.put(e,new Node<>(e));
    }

    public Node<E> findRoot(E e){
        Node<E> node=map.get(e);
        if(node==null)return null;
        while(!Objects.equals(node.element,node.parent.element)){
            node.parent=node.parent.parent;
            node=node.parent;
        }
        return node;
    }

    public void union(E e1,E e2){
       Node<E> node1= findRoot(e1);
       Node<E> node2= findRoot(e2);
       if(node1==null || node2==null)return;
       if(Objects.equals(node1.element,node2.element))return;
       if(node1.rank<node2.rank){
           //node1嫁接到node2上
           node1.parent=node2;
       }else if(node1.rank>node2.rank){
           //node2嫁接到node1上
           node2.parent=node1;
       }else{
           //node1和node2相等
           node1.parent=node2;
           node2.rank+=1;
       }

    }
    public E find(E e){
        Node<E> node=findRoot(e);
        return node==null?null:node.element;
    }

    public boolean isSameSet(E e1,E e2){
        return Objects.equals(find(e1),find(e2));
    }


    static class Node<E>{
        E element;
        Node<E> parent=this;
        int rank=1;
        public Node(E element){
            this.element=element;
        }
    }
}
